`
https://leetcode.cn/problems/design-a-number-container-system/
`

class NumberContainers {
  constructor() {
    this.store = new Map()
    this.pqs = new Map()
  }

  /** 
   * @param {number} index 
   * @param {number} number
   * @return {void}
   */
  change(index, number) {
    // 设置 index 位置的数字为 number
    this.store.set(index, number)
    // 获取 number 对应的优先队列
    let pq = this.pqs.get(number)
    if (!pq) {
      this.pqs.set(number, pq = new _Heap())
    }
    // 将 index 添加到对应的优先队列中
    pq.push(index)
  }

  /** 
   * @param {number} number
   * @return {number}
   */
  find(number) {
    // 找到 number 对应的优先队列
    const pq = this.pqs.get(number)
    if (!pq || pq.isEmpty()) return -1
    // 惰性删除
    while (!pq.isEmpty()) {
      const idx = pq.peek()
      // 在获取 number 的下标最小值时，需要先校验优先队列堆顶下标对应的数字是否等于 number
      // 不等于时直接丢弃，等于则返回该下标
      if (this.store.get(idx) === number) return idx
      pq.pop()
    }
    // 如果优先队列为空，则返回 −1
    return -1
  }
}

class _Heap {
  constructor(compare) {
    this.heap = []
    const rawCompare = compare || ((a, b) => a - b)
    this.compare = ((a, b) => -rawCompare(a, b))
  }

  size() {
    return this.heap.length
  }

  isEmpty() {
    return this.size() === 0
  }

  peek() {
    return this.heap[0]
  }

  push(val) {
    this.heap.push(val)
    this.bubbleUp(this.heap.length - 1)
  }

  pop() {
    if (this.isEmpty()) return undefined
    const top = this.heap[0]
    const last = this.heap.pop()
    if (!this.isEmpty()) {
      this.heap[0] = last
      this.sinkDown(0)
    }
    return top
  }

  bubbleUp(idx) {
    let current = idx
    while (current > 0) {
      const parent = this.parent(current)
      if (this.compare(this.heap[current], this.heap[parent]) > 0) {
        this.swap(current, parent)
        current = parent
      } else break
    }
  }

  sinkDown(idx) {
    let current = idx
    const len = this.size()
    while (true) {
      const left = this.left(current)
      const right = this.right(current)
      let target = current

      if (left < len && this.compare(this.heap[left], this.heap[target]) > 0) {
        target = left
      }

      if (right < len && this.compare(this.heap[right], this.heap[target]) > 0) {
        target = right
      }

      if (target !== current) {
        this.swap(target, current)
        current = target
      } else break
    }
  }

  swap(idx1, idx2) {
    [this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]]
  }

  parent(idx) {
    return Math.floor((idx - 1) / 2)
  }

  left(idx) {
    return idx * 2 + 1
  }

  right(idx) {
    return idx * 2 + 2
  }
}

/** 
 * Your NumberContainers object will be instantiated and called as such:
 * var obj = new NumberContainers()
 * obj.change(index,number)
 * var param_2 = obj.find(number)
 */